// 归并排序、逆序对
// https://www.luogu.com.cn/problem/P1908

int n;
ll cnt;
int a[maxn], temp[maxn];

void merge_sort(int l, int len) {
    if (len <= 1) return;
    merge_sort(l, len / 2);
    merge_sort(l + len / 2, len - len / 2);
    memcpy(temp, a + l, sizeof(int) * len);
    temp[len] = inf;
    for (int p = l, pl = 0, mid = len / 2, pr = mid; p < l + len; ++p) {
        if (pl >= mid || temp[pl] > temp[pr])
            a[p] = temp[pr++], cnt += mid - pl;
        else
            a[p] = temp[pl++];
    }
    // rf(i, len) printf("%d ", a[l + i - 1]);
    // puts("");
}
